package com.algorithm.liyc.practice;

import com.algorithm.liyc.entity.ListNode;

/**
 * 删除链表的倒数第N个节点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
 *
 * @author Liyc
 * @date 2023/11/23 17:26
 **/

public class Solution11 {
    /**
     *双指针
     */
    public ListNode removeNthFromEnd(ListNode head, int n){
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode slownode = dummy;
        ListNode fastnode = dummy;

        //只要快慢指针相差 n 个结点即可
        for (int i = 0; i < n; i++) {
            fastnode = fastnode.next;
        }

        while (fastnode.next != null) {
            slownode = slownode.next;
            fastnode = fastnode.next;
        }
        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slownode.next = slownode.next.next;
        return dummy.next;
    }
}
